1403. Арифметика Балу

Балу, ленивый бурый медведь, который обучает волчат Закону Джунглей. Он может бродить, где ему вздумается, потому что ест одни только орехи, мед и коренья.

Это случилось в то время, когда медведь Балу обучал Маугли Закону Джунглей. Большой и важный бурый медведь радовался способностям ученика, потому что волчата обычно выучивают из Закона Джунглей только то, что нужно их Стае и племени. Но Маугли, как детенышу человека, нужно было знать гораздо больше.

На занятиях по арифметике Балу придумал следующую игру. Надо было из числа 1 получить число n, при этом разрешалось текущее число либо умножить на три, либо к текущему числу прибавить 4. За каждое умножение Балу давал пять тумаков, а за каждое сложение 2 тумака. Например,

в первом случае получишь десять тумаков, во втором – двенадцать.

Маугли естественно лучше всех освоил арифметику и быстро придумал, как решить задачу, получив наименьшее количество тумаков. Он также заметил, что не всегда можно выполнить задание хитрого медведя…

Вход. Одно целое число n (1 ≤ n ≤ 10⁹).

Выход. Вывести минимальное количество тумаков, которые можно получить за решение задачи. Если решить задачу невозможно, то вывести число 0.

Пример входа	Пример выхода
21	10

РЕШЕНИЕ

структуры данных – map, рекурсия

Анализ алгоритма

Обозначим через f(n) минимальное количество тумаков, которые можно получить за решение задачи.

Тогда:

· f(n) = min (f(n / 3) + 5, f(n – 4) + 2 ), если n делится на 3.

· f(n) = f(n – 4) + 2 , если n не делится на 3.

Например, для n ≤ 10⁷ вычислим и запомним значения функции f(n) в линейном массиве m. Для больших значений n запоминания проведем в структуре map.

Реализация алгоритма

Объявим структуры для запоминания значений функции f(n).

#define MAX 10000000

int m[MAX];

map<int, int> mp;

Рекурсивное вычисление с запоминанием функции f(n).

int f(int n)

{

if (n < MAX) return m[n];

if (mp[n] > 0) return mp[n];

if (n % 3 == 0)

mp[n] = f(n/3) + 5;

else

mp[n] = f(n-4) + 2;

return mp[n];

}

Основная часть программы. Положим m[i] = - µ, если значение i Маугли получить не сможет никакими действиями. Вычислим f(i) для i до 10⁷ и запомним их в m[i].

m[0] = -MAX; m[1] = 0; m[2] = -MAX; m[3] = 5; m[4] = -MAX; m[5] = 2;

for(i = 6; i < MAX; i++)

if(i % 3 == 0)

m[i] = min(m[i / 3] + 5, m[i - 4] + 2);

else

m[i] = m[i - 4] + 2;

Читаем входное значение n. Вычисляем и выводим ответ.

scanf("%d",&n);

res = f(n);

Если res окажется меньше 0, то решить задачу невозможно, выводим число 0.

if (res < 0) res = 0;

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

static Map<Integer, Integer> mp = new HashMap<Integer, Integer>();

static int MAX = 10000000;

static int m[] = new int[MAX];

public static int f(int n)

{

if (n < MAX) return m[n];

if (mp.containsKey(n)) return mp.get(n);

if (n % 3 == 0)

mp.put(n,f(n/3) + 5);

else

mp.put(n,f(n-4) + 2);

return mp.get(n);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

m[0] = -MAX; m[1] = 0; m[2] = -MAX; m[3] = 5;

m[4] = -MAX; m[5] = 2;

for(int i = 6; i < MAX; i++)

if(i % 3 == 0)

m[i] = Math.min(m[i / 3] + 5, m[i - 4] + 2);

else

m[i] = m[i - 4] + 2;

int n = con.nextInt();

int res = f(n);

if (res < 0) res = 0;

System.out.println(res);

con.close();

}

}